package org.linearlist;

/**
 * @author: 默苍璃
 * @date: 2023-04-11 10:46
 * <p>
 * 循环队列
 * 顺序结构循环队列
 */
public class SequenceQueue<T> {
    final int MaxSize = 10;
    private T[] queueArray;

    /**
     * 允许删除的一端称为队头（front）
     * 允许插入的一端称为队尾（rear）
     */
    private int front, rear;


    /**
     * 队列的初始化
     * 构造一个空的队列
     */
    public SequenceQueue() {
        front = rear = 0;
        queueArray = (T[]) new Object[MaxSize];
    }


    /**
     * 入队
     * 在队列的队尾插入一个新元素
     *
     * @param obj
     */
    public void EnQueue(T obj) {
        //判断队列是否满了
        if ((rear + 1) % queueArray.length == front) {
            //队列扩容
            T[] p = (T[]) new Object[queueArray.length * 2];

            //处于循环队列末尾（没有发生首位移动）
            if (rear == ((T[]) queueArray).length - 1) {
                for (int i = 1; i <= rear; i++) {
                    p[i] = queueArray[i];
                }
            } else {
                int i, j = 1;
                for (i = front + 1; i < queueArray.length; i++, j++) {
                    p[j] = queueArray[i];
                }
                for (i = 0; i <= rear; i++, j++) {
                    p[j] = queueArray[i];
                }
                front = 0;
                rear = queueArray.length - 1;
            }
            queueArray = p;
        }
        rear = (rear + 1) % queueArray.length;
        queueArray[rear] = obj;
    }


    /**
     * 出队
     * 删除队列队头元素
     *
     * @return
     */
    public T DeQueue() {
        if (isEmpty()) {
            System.out.println("队列已空，无法出队！");
            return null;
        }
        front = (front + 1) % queueArray.length;
        return queueArray[front];
    }


    /**
     * 取头元素操作
     * 取队列队头元素
     *
     * @return
     */
    public T getTop() {
        if (isEmpty()) {
            System.out.println("队列已空，无法读取元素！");
            return null;
        }
        return queueArray[(front + 1) % queueArray.length];
    }


    /**
     * 求队列的长度
     * 求出队列中数据元素的个数
     *
     * @return
     */
    public int size() {
        return (rear - front + queueArray.length) % queueArray.length;
    }

    /**
     * 判断当前队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return front == rear;
    }


    /**
     * 遍历队列
     * 依次访问队列中每个元素并输出
     */
    public void nextOrder() {
        int i, j = front;
        for (i = 1; i <= size(); i++) {
            j = (j + 1) % queueArray.length;
            System.out.println(queueArray[j]);
        }
    }

    /**
     * 清空队列
     */
    public void clear() {
        front = rear = 0;
    }


}